void printArr(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}
int fact(int n){return n?fact(n-1)*n:1;}

int sumDigit(int n){
    return n<10?n:sumDigit(n/10)+(n%10);
}

int intLen(int n){
    return n<10?1:intLen(n/10)+1;
}

void rPrint(int n){
    if(n<10)
        printf("%d",n);
    else{
        printf("%d",n%10);
        rPrint(n/10);
    }
}

int pow(int x,int n){
    if(x==1||n==0)return 1;
    if(x==0||n==1)return x;
    if(n%2==0)
        return pow(x*x,n/2);
    return x*pow(x*x,n/2);
}

int gcd(int a,int b){ return b?gcd(b,a%b):a; }
int lcm(int a,int b){ return a/gcd(a,b)*b; }

int cnr(int n,int r){
    if(n==r||r==0)return 1;
    return cnr(n-1,r-1)+cnr(n-1,r);
}
